package cn.yuemouren.unionfind.impl;

import cn.yuemouren.unionfind.UnionFind;
import javafx.scene.Parent;

/**
 * @Author: Timi
 * @Description: 并查集基于rank优化
 * @Date: 2020/7/12 18:07
 * @Version: v1.0
 */
public class UnionFindImpl4 implements UnionFind {
    private int[] parent;
    private int[] rank; //用于保存节点数量的数组

    public UnionFindImpl4(int size) {
        this.parent = new int[size];
        this.rank = new int[size];
        for (int i = 0; i < parent.length; i++){
            parent[i] = i;
            rank[i] = 1;
        }
    }

    /**
     * 向并查集中添加元素
     * @param p
     * @param q
     *  时间复杂度 O(logH) H是深度
     */
    @Override
    public void union(int p, int q) {
        int pParent = find(p);
        int qParent = find(q);

        if(pParent == qParent)
            return;

        if(rank[pParent] > rank[qParent]){
            parent[qParent] = pParent;
        } else if(rank[qParent] > rank[pParent]){
            parent[pParent] = qParent;
        } else {
            parent[pParent] = qParent;
        }
    }

    /**
     * 查看并查集中是否关联
     * @param p
     * @param q
     * @return
     * 时间复杂度 O(logH)
     */
    @Override
    public boolean isConnectioned(int p, int q) {
        return find(p) == find(q);
    }

    /**
     * 查找父索引的值
     * @param i
     * @return
     */
    private int find(int i){
        if(i < 0 || i >= parent.length)
            throw new IllegalArgumentException("param is fail");
        while (parent[i] != i)//只有父节点值才自己指向自己
            i = parent[i];
        return parent[i];
    }
}
